package meiriyiti

import (
	"fmt"
	"sort"
)

func kthSmallestProduct(nums1 []int, nums2 []int, k int64) int64 {
	zheng := make([]int, 0)
	fu := make([]int, 0)
	l1, l2 := len(nums1), len(nums2)
	for n1 := 0; n1 < l1; n1++ {
		for n2 := 0; n2 < l2; n2++ {
			num1, num2 := nums1[n1], nums2[n2]
			if (num1 > 0 && num2 < 0) || (num1 < 0 && num2 > 0) {
				fu = append(fu, num1*num2)
			} else {
				zheng = append(zheng, num1*num2)
			}
		}

	}
	fmt.Println(fu, zheng)
	if int64(len(fu)) > k {
		sort.Ints(fu)
		return int64(fu[k-1])
	} else {
		sort.Ints(zheng)
		return int64(zheng[int(k)-len(fu)-1])
	}
}
func Abs(num int) int {
	if num < 0 {
		return -num
	}
	return num
}

func kthSmallestProduct1(nums1 []int, nums2 []int, k int64) int64 {
	n1, n2 := len(nums1), len(nums2)
	pos1, pos2 := 0, 0
	for pos1 < n1 && nums1[pos1] < 0 {
		pos1++
	}
	for pos2 < n2 && nums2[pos2] < 0 {
		pos2++
	}
	left, right := int64(-1e10), int64(1e10)
	for left <= right {
		mid := (left + right) / 2
		count := int64(0)
		i1, i2 := 0, pos2-1
		for i1 < pos1 && i2 >= 0 {
			if int64(nums1[i1])*int64(nums2[i2]) > mid {
				i1++
			} else {
				count += int64(pos1 - i1)
				i2--
			}
		}
		i1, i2 = pos1, n2-1
		for i1 < n1 && i2 >= pos2 {
			if int64(nums1[i1])*int64(nums2[i2]) > mid {
				i2--
			} else {
				count += int64(i2 - pos2 + 1)
				i1++
			}
		}
		i1, i2 = 0, pos2
		for i1 < pos1 && i2 < n2 {
			if int64(nums1[i1])*int64(nums2[i2]) > mid {
				i2++
			} else {
				count += int64(n2 - i2)
				i1++
			}
		}
		i1, i2 = pos1, 0
		for i1 < n1 && i2 < pos2 {
			if int64(nums1[i1])*int64(nums2[i2]) > mid {
				i1++
			} else {
				count += int64(n1 - i1)
				i2++
			}
		}
		if count < k {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return left
}
